{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Next Greater Element II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: nextGreaterElements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #下一个更大元素 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个循环数组&nbsp;<code>nums</code>&nbsp;（&nbsp;<code>nums[nums.length - 1]</code>&nbsp;的下一个元素是&nbsp;<code>nums[0]</code>&nbsp;），返回&nbsp;<em><code>nums</code>&nbsp;中每个元素的 <strong>下一个更大元素</strong></em> 。</p>\n",
    "\n",
    "<p>数字 <code>x</code>&nbsp;的 <strong>下一个更大的元素</strong> 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 <code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,2,1]\n",
    "<strong>输出:</strong> [2,-1,2]\n",
    "<strong>解释:</strong> 第一个 1 的下一个更大的数是 2；\n",
    "数字 2 找不到下一个更大的数； \n",
    "第二个 1 的下一个最大的数需要循环搜索，结果也是 2。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,2,3,4,3]\n",
    "<strong>输出:</strong> [2,3,4,-1,4]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup>&nbsp;&lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [next-greater-element-ii](https://leetcode.cn/problems/next-greater-element-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [next-greater-element-ii](https://leetcode.cn/problems/next-greater-element-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,1]', '[1,2,3,4,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        nums1 = nums + nums\n",
    "        res = [-1] * len(nums)\n",
    "\n",
    "        for i, each in enumerate(nums):\n",
    "            for idx_ in range(i+1, len(nums1)):\n",
    "                if nums1[idx_] > each:\n",
    "                    res[i] = nums1[idx_]\n",
    "                    break\n",
    "\n",
    "        return res\n",
    "\n",
    "        # for i, each in enumerate(nums1):\n",
    "        #     idx = nums2.index(each)\n",
    "            \n",
    "        #     for idx_ in range(idx+1, len(nums2)):\n",
    "                \n",
    "        #         if nums2[idx_] > each:\n",
    "                    \n",
    "        #             res[i] = nums2[idx_]\n",
    "        #             break\n",
    "\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        nums_double = nums + nums\n",
    "        stack = [0]\n",
    "        recoder = [0] * len(nums_double)\n",
    "\n",
    "        for i in range(1, len(nums_double)):\n",
    "            while len(stack) and nums_double[i] > nums_double[stack[-1]]:\n",
    "                recoder[stack[-1]] = i - stack[-1]\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "\n",
    "        result = [-1] * len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if recoder[i] != 0:\n",
    "                result[i] = nums_double[i + recoder[i]]\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        ans=[]\n",
    "        for i in range(len(nums)):\n",
    "            j=0\n",
    "            n=0\n",
    "            for k in range(i+1,len(nums)+i):\n",
    "                \n",
    "                \n",
    "                if k>=len(nums):\n",
    "                    k=j\n",
    "                    j=j+1\n",
    "                if nums[i]<nums[k] or k==i:\n",
    "                    if k==len(nums)+1:\n",
    "                        k==0\n",
    "                    ans.append(nums[k])\n",
    "                    n=1\n",
    "                    break\n",
    "                \n",
    "            if n==0:\n",
    "                ans.append(-1)\n",
    "        return ans\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        res = [-1]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            # idx = nums.index(i)\n",
    "            for j in range(i+1,len(nums)+i):\n",
    "                if nums[j%(len(nums))]>nums[i]:\n",
    "                    res[i] = nums[j%(len(nums))]\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        stk,res=[],[-1]*n\n",
    "        for i in range(n*2-1,-1,-1):\n",
    "            while stk and nums[i%n]>=stk[-1]:\n",
    "                stk.pop()\n",
    "            res[i%n]=stk[-1] if stk else -1\n",
    "            stk.append(nums[i%n])\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        result = [-1]*len(nums)\n",
    "        stack.append(0)\n",
    "        for i in range(1, 2*len(nums)):\n",
    "            if nums[i%len(nums)] < nums[stack[-1]]:\n",
    "                stack.append(i%len(nums))\n",
    "            elif nums[i%len(nums)] == nums[stack[-1]]:\n",
    "                stack.append(i%len(nums))\n",
    "            elif nums[i%len(nums)] > nums[stack[-1]]:\n",
    "                while stack and nums[i%len(nums)] > nums[stack[-1]]:\n",
    "                    result[stack[-1]] = nums[i%len(nums)]\n",
    "                    stack.pop()\n",
    "            stack.append(i%len(nums))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        res = [-1] * len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            j = i+1\n",
    "            while j%len(nums) != i:  \n",
    "\n",
    "                if nums[j%len(nums)] > nums[i]:\n",
    "                    res[i] = nums[j%len(nums)]\n",
    "                    # print(i,j)\n",
    "                    break\n",
    "                j += 1\n",
    "        \n",
    "        # for j in range(len(nums)-1):\n",
    "        #     if nums[j] > nums[len(nums)-1]:\n",
    "        #         res[len(nums)-1] = nums[j]\n",
    "        #         break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        res = [-1]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)+i):\n",
    "                if nums[j%(len(nums))]>nums[i]:\n",
    "                    res[i] = nums[j%len(nums)]\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        N = len(nums)\n",
    "        res = [-1] * N\n",
    "        for i in range(N):\n",
    "            k = i + 1\n",
    "            cnt = N - 1 \n",
    "            while cnt > 0: \n",
    "                if k < N: \n",
    "                    if nums[k] > nums[i]: \n",
    "                        res[i] = nums[k]\n",
    "                        break    \n",
    "                else:\n",
    "                    if nums[k-N] > nums[i]: \n",
    "                        res[i] = nums[k-N]\n",
    "                        break\n",
    "                k += 1\n",
    "                cnt -= 1\n",
    "        return res\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        res = [-1 for _ in range(n)]\n",
    "        for i in range(n * 2 + 1, -1, -1):\n",
    "            while stack and nums[i % n] >= stack[-1]:\n",
    "                stack.pop()\n",
    "            res[i % n] = stack[-1] if stack else -1 \n",
    "            stack.append(nums[i % n])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        n = len(nums)\n",
    "        res = [0]*n\n",
    "\n",
    "        if n == 0 or n == 1:\n",
    "            return [-1]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, i+n):\n",
    "                if nums[j%n] > nums[i]:\n",
    "                    res[i] = nums[j%n]\n",
    "                    break\n",
    "                else:\n",
    "                    res[i] = -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [-1] * n\n",
    "        stack = []\n",
    "        for i in range(2*n-1, -1, -1):\n",
    "            while stack and nums[i%n] >= stack[-1]:\n",
    "                stack.pop()\n",
    "            res[i%n] = stack[-1] if stack else -1\n",
    "            stack.append(nums[i%n])\n",
    "        return res\n",
    "        \n",
    "        # numsNew = nums * 2\n",
    "        # res = [-1] * len(numsNew)\n",
    "        # stack = []\n",
    "        # for i in range(len(numsNew)-1, -1, -1):\n",
    "        #     while stack and numsNew[i] >= stack[-1]:\n",
    "        #         stack.pop()\n",
    "        #     res[i] = stack[-1] if stack else -1\n",
    "        #     stack.append(numsNew[i])\n",
    "        # return res[:len(nums)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        result = []\n",
    "        for i in range(len(nums)):\n",
    "            j = (i+1)%len(nums)\n",
    "            while j!=i:\n",
    "                if nums[j]>nums[i]:\n",
    "                    result.append(nums[j])\n",
    "                    break\n",
    "                j=(j+1)%len(nums)\n",
    "            if j==i:\n",
    "                result.append(-1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        res = [-1] * len(nums)\n",
    "        stack = []\n",
    "        for i in range(2*len(nums)-1, -1, -1):\n",
    "            while stack and nums[i%len(nums)] >= stack[-1]:\n",
    "                stack.pop()\n",
    "            res[i%len(nums)] = stack[-1] if stack else -1\n",
    "            stack.append(nums[i%len(nums)])\n",
    "        return res\n",
    "        \n",
    "        # numsNew = nums * 2\n",
    "        # res = [-1] * len(numsNew)\n",
    "        # stack = []\n",
    "        # for i in range(len(numsNew)-1, -1, -1):\n",
    "        #     while stack and numsNew[i] >= stack[-1]:\n",
    "        #         stack.pop()\n",
    "        #     res[i] = stack[-1] if stack else -1\n",
    "        #     stack.append(numsNew[i])\n",
    "        # return res[:len(nums)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1]*n \n",
    "        maxn = max(nums)\n",
    "        stack = [maxn]\n",
    "        index = nums.index(maxn)\n",
    "\n",
    "        for i in range(index-1, -1, -1):\n",
    "            while nums[i] >= stack[-1]:\n",
    "                stack.pop()\n",
    "            ans[i] = stack[-1]\n",
    "            stack.append(nums[i])\n",
    "        for i in range(n-1, index, -1):\n",
    "            while stack and nums[i] >= stack[-1]:\n",
    "                stack.pop()\n",
    "            ans[i] = stack[-1] if stack else -1\n",
    "            stack.append(nums[i])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [-1] * n\n",
    "        stk = deque()\n",
    "        \n",
    "        for i in range(n - 2, -1, -1):\n",
    "            while stk and nums[i] > stk[-1]:\n",
    "                stk.pop()\n",
    "            stk.append(nums[i])\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and nums[i] >= stk[-1]:\n",
    "                stk.pop()\n",
    "            while stk and len(stk) >= n:\n",
    "                stk.popleft()\n",
    "            if stk:\n",
    "                res[i] = stk[-1]\n",
    "            stk.append(nums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        if n == 0 or n == 1:\n",
    "            return [-1]\n",
    "            \n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                for j in range(1,n):\n",
    "                    maxnum = max(nums[i],nums[j])\n",
    "                    if maxnum != nums[i]:\n",
    "                        res.append(maxnum)\n",
    "                        break\n",
    "                if maxnum == nums[i]:\n",
    "                    res.append(-1)\n",
    "            \n",
    "            elif i == n-1:\n",
    "                for j in range(n-1):\n",
    "                    maxnum = max(nums[i],nums[j])\n",
    "                    if maxnum != nums[i]:\n",
    "                        res.append(maxnum)\n",
    "                        break\n",
    "                if maxnum == nums[i]:\n",
    "                    res.append(-1)\n",
    "            \n",
    "            else:\n",
    "                for j in range(i+1,n):\n",
    "                    maxnum = max(nums[i],nums[j])\n",
    "                    if maxnum != nums[i]:\n",
    "                        res.append(maxnum)\n",
    "                        break\n",
    "                    elif j == n-1 and maxnum == nums[i]:\n",
    "                        for j in range(i):\n",
    "                            maxnum = max(nums[i],nums[j])\n",
    "                            if maxnum != nums[i]:\n",
    "                                res.append(maxnum)\n",
    "                                break\n",
    "                if maxnum == nums[i]:\n",
    "                    res.append(-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        res = [-1] * n\n",
    "\n",
    "        for i in range(2*n):\n",
    "            while stack and nums[stack[-1]] < nums[i%n]:\n",
    "                res[stack.pop()] = nums[i%n]\n",
    "            # if stack:\n",
    "            #     res[stack[-1]%n] = -1\n",
    "            stack.append(i%n)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        q = []\n",
    "        ans = [-1] * n\n",
    "        for i in range(n*2-1):\n",
    "            i = i % n\n",
    "            while q and nums[q[-1]] < nums[i]:\n",
    "                pos = q.pop()\n",
    "                ans[pos] = nums[i]\n",
    "            q.append(i)\n",
    "            # print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        res = [-1] * len(nums)\n",
    "        \n",
    "        stack = []\n",
    "        for i in range(len(nums) * 2):\n",
    "            index = i % len(nums)\n",
    "            while stack and nums[index] > nums[stack[-1]]:\n",
    "                res[stack.pop()] = nums[index]\n",
    "            stack.append(index)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        nexts = [-1] * len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            while (len(stack) != 0 and nums[i] > nums[stack[-1]]):\n",
    "                nexts[stack.pop()] = nums[i]\n",
    "            stack.append(i)\n",
    "        for i in range(len(nums)):\n",
    "            while (len(stack) != 0 and nums[i] > nums[stack[-1]]):\n",
    "                nexts[stack.pop()] = nums[i]\n",
    "        return nexts\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        res = [-1] * len(nums)\n",
    "        stack = []\n",
    "        for i in range(2*len(nums)):\n",
    "            i = i % len(nums)\n",
    "            while stack and nums[i] > nums[stack[-1]]:\n",
    "                index = stack.pop()\n",
    "                res[index] = nums[i]\n",
    "            stack.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [-1] * n\n",
    "        stack = []\n",
    "\n",
    "        for i in range(2 * n - 1, -1, -1): # DOUBLE lenght of array to deal with loop\n",
    "            while stack and stack[-1] <= nums[i % n]: \n",
    "                stack.pop()\n",
    "            res[i % n] = -1 if not stack else stack[-1]\n",
    "            stack.append(nums[i % n])\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ret = [-1] * n\n",
    "        stk = list()\n",
    "        for i in range(n * 2 - 1):\n",
    "            while stk and nums[stk[-1]] < nums[i % n]:\n",
    "                ret[stk.pop()] = nums[i%n]\n",
    "            stk.append(i % n)\n",
    "        return  ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        s = []\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(2*n - 1, -1, -1):\n",
    "            while s and s[-1] <= nums[i % n]:\n",
    "                s.pop()\n",
    "            if i < n:\n",
    "                res.append(s[-1] if s else -1)\n",
    "            s.append(nums[i % n])\n",
    "        res.reverse()\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        res = [-1]*len(nums)\n",
    "        l = len(nums)\n",
    "        for i in range(len(nums)*2):\n",
    "            while stack and nums[stack[-1]] < nums[i%l]:\n",
    "                index = stack.pop()\n",
    "                res[index] = nums[i%l]\n",
    "            stack.append(i%l)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "#         size = len(nums)\n",
    "\n",
    "#         if size == 1:\n",
    "#             return [-1]\n",
    "\n",
    "#         nums.extend(nums)\n",
    "#         res = [-1] * 2 * size\n",
    "#         stack = []\n",
    "\n",
    "#         for i in range(2 * size):\n",
    "#             while stack and nums[i] > nums[stack[-1]]:\n",
    "#                 idx = stack.pop()\n",
    "#                 res[idx] = nums[i]\n",
    "            \n",
    "#             stack.append(i)\n",
    "        \n",
    "#         return res[:size]\n",
    "            \n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        size = len(nums)\n",
    "\n",
    "        if size == 1:\n",
    "            return [-1]\n",
    "\n",
    "\n",
    "        res = [-1] * size\n",
    "        stack = []\n",
    "\n",
    "        for i in range(2 * size - 1):\n",
    "            while stack and nums[i % size] > nums[stack[-1]]:\n",
    "\n",
    "                res[stack.pop()] = nums[i % size]\n",
    "            \n",
    "            stack.append(i % size)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        # 5 4 3 2 1 5 4 3 2 \n",
    "        # 0 1 2 3 4 0 1 2 3\n",
    "        ans = [-1] * n\n",
    "        stack = []\n",
    "        for i in range(2 * n - 1):\n",
    "            while stack and nums[stack[-1]] < nums[i % n]:\n",
    "                ans[stack.pop()] = nums[i % n]\n",
    "            stack.append(i % n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, n: List[int]) -> List[int]:\n",
    "        l=[-1]*len(n)\n",
    "        for i in range(len(n)):\n",
    "            s=n[i+1:]+n[0:i]\n",
    "            for a in s:\n",
    "                if a>n[i]:\n",
    "                    l[i]=a\n",
    "                    break\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        res = [-1] * n\n",
    "        for i in range(2 * n - 1):\n",
    "            while stack and nums[stack[-1]] < nums[i % n]:\n",
    "                cur = stack.pop()\n",
    "                res[cur] = nums[i % n]\n",
    "            stack.append(i % n)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # n = len(nums)\n",
    "        # res = [-1] * n\n",
    "        # # stack = []\n",
    "        # # for i in range(2 * n - 1):\n",
    "        # #     while stack and nums[stack[-1]] < nums[i % n]:\n",
    "        # #         cur = stack.pop()\n",
    "        # #         res[cur] = nums[i % n]\n",
    "\n",
    "        # #     stack.append(i % n)\n",
    "\n",
    "        # # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        idx = nums.index(max(nums))\n",
    "        res = [-1] * n \n",
    "        stack = []\n",
    "        for i in range(idx+1, idx+1+n):\n",
    "            while(stack and nums[stack[-1]] < nums[i%n]):\n",
    "                res[stack.pop()] = nums[i%n]\n",
    "            stack.append(i%n)\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        # 循环数组 要循环的找 \n",
    "        # 单调栈 递增 \n",
    "        res = [-1] * len(nums)\n",
    "        stack = []\n",
    "        for i in range(len(nums)*2): # 至少遍历两次才能都找完 \n",
    "            while(len(stack) != 0 and nums[i%len(nums)] > nums[stack[-1]]):\n",
    "                    # 如果栈非空且 当前元素（当前元素可以是第二次循环过来的 所以求模）大于栈顶\n",
    "                    # 处理 + 弹栈 \n",
    "                    res[stack[-1]] = nums[i%len(nums)] # 记录下一个更大的值作为答案\n",
    "                    stack.pop()\n",
    "            stack.append(i%len(nums)) # 栈里记录位置 \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        # 循环数组 要循环的找 \n",
    "        # 单调栈 递增 \n",
    "        res = [-1] * len(nums)\n",
    "        stack = []\n",
    "        for i in range(len(nums)*2): # 至少遍历两次才能都找完 \n",
    "            while(len(stack) != 0 and nums[i%len(nums)] > nums[stack[-1]]):\n",
    "                    # 如果栈非空且 当前元素（当前元素可以是第二次循环过来的 所以求模）大于栈顶\n",
    "                    # 处理 + 弹栈 \n",
    "                    res[stack[-1]] = nums[i%len(nums)] # 记录下一个\n",
    "                    stack.pop()\n",
    "            stack.append(i%len(nums))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = [] \n",
    "        res = [-1] * n \n",
    "        for i in range(2*n):\n",
    "            while stack and nums[stack[-1] % n] < nums[i%n]:\n",
    "                res[stack[-1]%n] = nums[i%n]\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        stack = []\n",
    "        for i in range(n * 2):\n",
    "            while stack and nums[i % n] > nums[stack[-1]]:\n",
    "                cur = stack.pop()\n",
    "                ans[cur] = nums[i % n]          \n",
    "            stack.append(i % n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        res = [-1] * len(nums)\n",
    "        stk = []\n",
    "        for i in range(len(nums)*2):\n",
    "            while stk and nums[i%len(nums)] > nums[stk[-1]]:\n",
    "                res[stk[-1]] = nums[i%len(nums)]\n",
    "                stk.pop()\n",
    "            stk.append(i%len(nums))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = [] \n",
    "        res = [-1] * n \n",
    "        for i in range(2*n):\n",
    "            # while stack and nums[stack[-1] % n] < nums[i%n]:\n",
    "            #     res[stack[-1]%n] = nums[i%n]\n",
    "            #     stack.pop()\n",
    "            # stack.append(i)\n",
    "            while stack and nums[stack[-1]] < nums[i%n]:\n",
    "                res[stack[-1]] = nums[i%n] \n",
    "                stack.pop()\n",
    "            stack.append(i%n)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        dp = [-1] * len(nums)\n",
    "        stack = []\n",
    "        for i in range(len(nums)*2):\n",
    "            while(len(stack) != 0 and nums[i%len(nums)] > nums[stack[-1]]):\n",
    "                    dp[stack[-1]] = nums[i%len(nums)]\n",
    "                    stack.pop()\n",
    "            stack.append(i%len(nums))\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        ans = [-1] * len(nums)*2\n",
    "\n",
    "        stk = []\n",
    "        nums += nums\n",
    "\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            while stk and stk[-1] <= nums[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                ans[i] = stk[-1]\n",
    "            stk.append(nums[i])\n",
    "        \n",
    "        return ans[:len(nums)//2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [-1]*n \n",
    "        s = []\n",
    "        for i in range(2*n-1, -1, -1):\n",
    "            while s and s[-1] <= nums[i % n]:\n",
    "                s.pop()\n",
    "            if s:\n",
    "                res[i % n] = s[-1]\n",
    "            s.append(nums[i % n])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        # 维护一个单调递减栈\n",
    "        # 待入栈元素>栈顶元素，出栈\n",
    "        # 待入栈元素为所求\n",
    "        n=len(nums)\n",
    "        nums.extend(nums[:n-1])\n",
    "\n",
    "        stack = []\n",
    "        res= [-1]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            while stack and nums[stack[-1]] < nums[i]:\n",
    "                res[stack.pop()] = nums[i]\n",
    "            stack.append(i)\n",
    "        return res[:n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        n = len(nums)\n",
    "        res = [-1] * len(nums)\n",
    "        nums = nums[::-1]\n",
    "        nums = nums + nums\n",
    "        \n",
    "\n",
    "        for i in range(len(nums)-1):\n",
    "            while stack and stack[-1] <= nums[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                if nums[i] < stack[-1]:\n",
    "                    res[i % n] = stack[-1]\n",
    "            stack.append(nums[i])\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        stack,hashmap = [],{}\n",
    "        nums2 = nums + nums\n",
    "        result = [-1 for _ in nums2]\n",
    "        for i in range(len(nums2)):\n",
    "            while stack and nums2[stack[-1]] < nums2[i]:\n",
    "                result[stack.pop()] = nums2[i]\n",
    "            stack.append(i)\n",
    "        \n",
    "        return result[:len(nums)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        q = deque([])\n",
    "        n = len(nums)\n",
    "        ans = [-1]*n\n",
    "        for i in range(2*n-1):\n",
    "            while q and nums[i%n] > nums[q[-1]]:\n",
    "                ans[q.pop()] = nums[i%n]\n",
    "            q.append(i%n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        cycle = nums * 2\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        stack = []\n",
    "        for i in range(2*n):\n",
    "            while stack and cycle[stack[-1]] < cycle[i]:\n",
    "                temp = stack.pop()\n",
    "                index = temp % n\n",
    "                ans[index] = cycle[i]\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        nums += nums\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] < nums[i]:\n",
    "                idx = stack.pop()\n",
    "                ans[idx] = nums[i]\n",
    "            stack.append(i)\n",
    "        return ans[:n//2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        nums2=nums+nums\n",
    "        res=[-1]*len(nums2)\n",
    "        stack=[]\n",
    "        for i in range(len(nums2)):\n",
    "            while stack and nums2[stack[-1]]<nums2[i]:\n",
    "                index=stack.pop()\n",
    "                res[index]=nums2[i]\n",
    "            stack.append(i)\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "        return res[:len(nums)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        # 维护一个单调递减栈\n",
    "        # 待入栈元素>栈顶元素，出栈\n",
    "        # 待入栈元素为所求\n",
    "        n=len(nums)\n",
    "        nums.extend(nums[:n-1])\n",
    "\n",
    "        stack = []\n",
    "        res= [-1]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            while stack and nums[stack[-1]] < nums[i]:\n",
    "                res[stack.pop()] = nums[i]\n",
    "            stack.append(i)\n",
    "        return res[:n]\n",
    "\n",
    "# 不需要显性地将该循环数组「拉直」，而只需要在处理时对下标取模即可\n",
    "        # for i in range(n * 2 - 1):\n",
    "        #     while stk and nums[stk[-1]] < nums[i % n]:\n",
    "        #         ret[stk.pop()] = nums[i % n]\n",
    "        #     stk.append(i % n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums):\n",
    "        n=len(nums)\n",
    "        ans=[-1]*n\n",
    "        nums=nums*2\n",
    "        q=collections.deque()\n",
    "        for i in range(len(nums)):\n",
    "            if i==0:\n",
    "                q.appendleft(i)\n",
    "            elif i<n:\n",
    "                while len(q)!=0 and nums[i]>nums[q[0]]:\n",
    "                    ans[q[0]]=nums[i]\n",
    "                    q.popleft()\n",
    "                q.appendleft(i)\n",
    "            else:\n",
    "                while nums[i]>nums[q[0]]:\n",
    "                    ans[q[0]]=nums[i]\n",
    "                    q.popleft()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        '''\n",
    "        #遍历两遍数组\n",
    "        stack=[]\n",
    "        res=[-1]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            while stack and nums[i]>nums[stack[-1]]:\n",
    "                cur=stack.pop()\n",
    "                res[cur]=nums[i]\n",
    "            stack.append(i)\n",
    "        for i in range(len(nums)):\n",
    "            while stack and nums[i]>nums[stack[-1]]:\n",
    "                cur=stack.pop()\n",
    "                res[cur]=nums[i]\n",
    "        return res\n",
    "        '''\n",
    "        #直接将数组扩大两倍\n",
    "        stack=[]\n",
    "        nums=nums*2\n",
    "        res=[-1]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            while stack and nums[i]>nums[stack[-1]]:\n",
    "                cur=stack.pop()\n",
    "                res[cur]=nums[i]\n",
    "            stack.append(i)\n",
    "        return res[:len(nums)//2]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * 2*n\n",
    "        stk = []\n",
    "        double_nums = nums + nums\n",
    "\n",
    "        for i,num in enumerate(double_nums):\n",
    "            while stk and num > double_nums[stk[-1]]:\n",
    "                pop_index = stk.pop()\n",
    "                ans[pop_index] = num\n",
    "            \n",
    "            stk.append(i)\n",
    "        return ans[:n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums = nums + nums\n",
    "        right = [-1] *  (2*n) \n",
    "        stack = []\n",
    "        for i in range(2*n-1, -1, -1):\n",
    "            while len(stack) != 0 and nums[stack[-1]] <= nums[i]:\n",
    "                stack.pop()\n",
    "            if len(stack) != 0:\n",
    "                right[i] = nums[stack[-1]]\n",
    "            stack.append(i)\n",
    "        return right[:n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        nums_2 = nums+nums\n",
    "        n = len(nums_2)\n",
    "        print(nums_2)\n",
    "        ans = [-1 for i in range(n)]\n",
    "        #initialize stack\n",
    "        stack = []\n",
    "        #itereta nums 2 times\n",
    "        for i in range(n):\n",
    "            cur_num = nums_2[i]\n",
    "            while stack and cur_num>nums_2[stack[-1]]:\n",
    "                ind = stack.pop()\n",
    "                ans[ind] = cur_num\n",
    "\n",
    "            stack.append(i)\n",
    "            #print(stack)\n",
    "        half_n = int(n/2)\n",
    "        ans = ans[:half_n]\n",
    "        print(ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        nums_2 = nums+nums\n",
    "        n = len(nums_2)\n",
    "        print(nums_2)\n",
    "        ans = [-1 for i in range(n)]\n",
    "        #initialize stack\n",
    "        stack = []\n",
    "        #itereta nums 2 times\n",
    "        for i in range(n):\n",
    "            cur_num = nums_2[i]\n",
    "            while stack and cur_num>nums_2[stack[-1]]:\n",
    "                ind = stack.pop()\n",
    "                ans[ind] = cur_num\n",
    "\n",
    "            stack.append(i)\n",
    "            #print(stack)\n",
    "        half_n = int(n/2)\n",
    "        ans = ans[:half_n]\n",
    "        print(ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        nums += nums\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        ans = [-1] * n\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] < nums[i]:\n",
    "                idx = stack.pop()\n",
    "                ans[idx] = nums[i]\n",
    "            stack.append(i)\n",
    "        return ans[:n//2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        stack,hashmap = [],{}\n",
    "        nums2 = nums + nums\n",
    "        result = [-1 for _ in nums]\n",
    "        for i in range(len(nums2)):\n",
    "            while stack and nums2[stack[-1]] < nums2[i]:\n",
    "                index = stack.pop()\n",
    "                if index < len(result):\n",
    "                    result[index] = nums2[i]\n",
    "            stack.append(i)\n",
    "        \n",
    "        return result[:len(nums)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        temp = nums[:]+nums[:]\n",
    "        n = len(nums)\n",
    "        ans = [-1 for _ in range(2*n)]\n",
    "        st = []\n",
    "        for index,num in enumerate(temp):\n",
    "            while st and num > temp[st[-1]]:\n",
    "                i = st.pop()\n",
    "                ans[i] = num\n",
    "            st.append(index)\n",
    "        st = []\n",
    "        return ans[:n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [-1 for _ in range(len(nums))]\n",
    "        nums.extend(nums)\n",
    "        stack = []\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if stack ==[]:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                if nums[stack[-1]]>= nums[i]:\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    while stack!=[] and nums[stack[-1]]< nums[i]  :\n",
    "                        index = stack.pop(-1)%n\n",
    "                        res[index] = nums[i]\n",
    "                    stack.append(i)\n",
    "        # last = stack.pop(-1)\n",
    "        # res[last] = -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        l = len(nums)\n",
    "        ret = [0] * l\n",
    "        stack = [(0, nums[0])] # (position, value) stack 剩下的是单调递减[包括相等的情况]\n",
    "        i = 1\n",
    "        second = False\n",
    "        while i<l:\n",
    "            v = nums[i]\n",
    "            # print(stack[-1])\n",
    "            while stack and v > stack[-1][1]:\n",
    "                k = stack.pop()\n",
    "                ret[k[0]] = v          \n",
    "            stack.append((i, v))      \n",
    "            i += 1\n",
    "            if not second and i >=l :\n",
    "                second = True\n",
    "                i = 0\n",
    "            if second and stack[0][-1] == stack[-1][-1]:\n",
    "                break\n",
    "        for i, v in stack:       \n",
    "            ret[i] = -1\n",
    "        return ret\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        l = nums + nums[:-1]\n",
    "        stack = []\n",
    "        re = [''] * len(nums)\n",
    "        for i in range(len(l)):\n",
    "            while stack and l[i] > l[stack[-1]]:\n",
    "                rei = stack.pop()\n",
    "                if rei < len(nums):\n",
    "                    re[rei] = l[i]    \n",
    "            stack.append(i)\n",
    "        re = [-1 if i == '' else i for i in re]\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        nums_2 = nums+nums\n",
    "        n = len(nums_2)\n",
    "        print(nums_2)\n",
    "        ans = [-1 for i in range(n)]\n",
    "        #initialize stack\n",
    "        stack = []\n",
    "        #itereta nums 2 times\n",
    "        for i in range(n):\n",
    "            cur_num = nums_2[i]\n",
    "            #如果当前数比最新进stack的数字大\n",
    "            while stack and cur_num>nums_2[stack[-1]]:\n",
    "                ind = stack.pop()\n",
    "                ans[ind] = cur_num\n",
    "\n",
    "            stack.append(i)\n",
    "            #print(stack)\n",
    "        half_n = int(n/2)\n",
    "        ans = ans[:half_n]\n",
    "        print(ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        l = len(nums)\n",
    "        ret = [0] * l\n",
    "        stack = [(0, nums[0])] # (position, value) stack 剩下的是单调递减[包括相等的情况]\n",
    "        i = 1\n",
    "        second = False\n",
    "        while i<=l:\n",
    "            idx = i % l\n",
    "            v = nums[idx]\n",
    "            # print(stack[-1])\n",
    "            while stack and v > stack[-1][1]:\n",
    "                k = stack.pop()\n",
    "                ret[k[0]] = v          \n",
    "            stack.append((idx, v))      \n",
    "            i += 1\n",
    "            if not second and i > l:\n",
    "                second = True\n",
    "                i = 0\n",
    "            if second and  stack[0][-1] == stack[-1][-1]:\n",
    "                break\n",
    "        for i, v in stack:       \n",
    "            ret[i] = -1\n",
    "        \"\"\"\n",
    "        # 栈 v 已经是单调递减（或者完全相等的数）首位肯定没有更大的值\n",
    "        ret[stack[0][0]] = -1\n",
    "        for i, v in stack[1:]:\n",
    "            if v == stack[0][1]:\n",
    "                ret[i] = -1\n",
    "            else:\n",
    "                ret[i] = stack[0][1]\n",
    "        \"\"\"\n",
    "        return ret\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        result = [-1] * len(nums)\n",
    "        stack = []\n",
    "        for index, value in enumerate(nums):\n",
    "            while stack and stack[-1][1] < value:\n",
    "                index_tmp, value_tmp = stack.pop()\n",
    "                result[index_tmp] = value\n",
    "            stack.append((index, value))\n",
    "        for index, value in enumerate(nums):\n",
    "            while stack and stack[-1][1] < value:\n",
    "                index_tmp, value_tmp = stack.pop()\n",
    "                result[index_tmp] = value\n",
    "            stack.append((index, value))\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        n_nums= nums.copy()\n",
    "        nums.extend(n_nums)\n",
    "        nums = nums[:-1]\n",
    "\n",
    "        ans = [-1 for _ in range(n)]\n",
    "    \n",
    "        # for i in range(n):\n",
    "        #     for j in range(i + 1, len(nums)):\n",
    "        #         if nums[j] > nums[i]:\n",
    "        #             ans[i] =nums[j]\n",
    "        #             break\n",
    "        # return ans\n",
    "\n",
    "\n",
    "        stack = []\n",
    "        for i in range(len(nums)):\n",
    "            while stack and nums[i] > nums[stack[-1]]:\n",
    "                ans[stack.pop()] = nums[i]\n",
    "            stack.append(i % n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        l=len(nums)\n",
    "        if l==1:\n",
    "            return [-1]\n",
    "        ans=[-1]*(l+l-1)\n",
    "        nums=nums+nums[0:l-1]\n",
    "        stk=[]\n",
    "        for i in range(l+l-1):\n",
    "            while stk and nums[stk[-1]]<nums[i]:\n",
    "                ans[stk.pop()]=nums[i]\n",
    "            stk.append(i)\n",
    "        return ans[:l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        ans = [-1 for i in range(len(nums))]\n",
    "        stack = []\n",
    "        for index in range(len(nums) * 2 - 1):\n",
    "            while stack and nums[index % len(nums)] > stack[-1][1]:\n",
    "                ans[stack[-1][0]] = nums[index % len(nums)]\n",
    "                stack.pop()\n",
    "            stack.append((index % len(nums), nums[index % len(nums)]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def nextGreaterElements(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        # 5 1 2 3 6\n",
    "        stk=[]\n",
    "        n=len(nums)\n",
    "        ans=[-1]*n\n",
    "        for i,c in enumerate(nums+nums):\n",
    "            while stk and stk[-1][1]<c:\n",
    "                t=stk.pop()\n",
    "                if t[0]>=n: continue\n",
    "                ans[t[0]]=c\n",
    "            stk.append((i,c))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, a: List[int]) -> List[int]:\n",
    "        n = len(a)\n",
    "        a = a + a\n",
    "        q = deque()\n",
    "        ans = [-1] * n\n",
    "        for i in range(n+n-1, -1, -1):\n",
    "            while q and q[0][0] <= a[i]:\n",
    "                q.popleft()\n",
    "            if i < n and q and q[0][1] - i < n:\n",
    "                ans[i] = q[0][0]\n",
    "            q.appendleft((a[i],i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        nums2 = nums + nums\n",
    "        stack = [0]\n",
    "        ans = [0] * len(nums2)\n",
    "        for i, x in enumerate(nums2):\n",
    "            while stack and x > nums2[stack[-1]]:\n",
    "                ans[stack[-1]] = i\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        res = [nums2[x] if x!=0 else -1 for x in ans]\n",
    "        return res[:len(nums)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [-1] * n\n",
    "        stack = []\n",
    "        i = 0\n",
    "        while i < 2*n:\n",
    "            cur = i % n\n",
    "            while stack and nums[cur] > stack[-1][0]:\n",
    "                val, index = stack.pop()\n",
    "                res[index] = nums[cur]\n",
    "            stack.append((nums[cur], cur))\n",
    "            i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        res = [-1] * len(nums)\n",
    "        stack = []\n",
    "        #print(list(range(len(nums)))+list(range(len(nums))))\n",
    "        for x, i in zip(nums+nums, list(range(len(nums)))+list(range(len(nums)))):\n",
    "\n",
    "            while stack and x > nums[stack[-1]]:\n",
    "                k = stack.pop(-1)\n",
    "                res[k] = x\n",
    "            stack.append(i)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stk = []\n",
    "        ans = [-1] * n\n",
    "        for i in range(2 * n - 1):\n",
    "            i = i % n\n",
    "            while stk and stk[-1][0] < nums[i]:\n",
    "                ans[stk[-1][1]] = nums[i]\n",
    "                stk.pop()\n",
    "            stk.append((nums[i], i))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        ms,hashmap = [],dict()\n",
    "        for i,num in enumerate(nums):\n",
    "            while len(ms) > 0 and nums[ms[-1]] < num: hashmap[ms.pop()] = num\n",
    "            ms.append(i)\n",
    "        for i,num in enumerate(nums):\n",
    "            while len(ms) > 0 and nums[ms[-1]] < num: \n",
    "                if ms[-1] not in hashmap: hashmap[ms[-1]] = num\n",
    "                ms.pop()\n",
    "            ms.append(i)\n",
    "        return [hashmap.get(i,-1) for i in range(len(nums))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        stack=[]\n",
    "        dic={}\n",
    "        res=[]\n",
    "        nums=nums*2\n",
    "        for i in nums[::-1]:\n",
    "            if not stack:\n",
    "                stack.append(i)\n",
    "            while stack and i>=stack[-1]:\n",
    "                stack.pop()\n",
    "            dic[i]=stack[-1] if stack else -1\n",
    "            stack.append(i)\n",
    "            res.append(dic[i])\n",
    "        return res[::-1][:len(nums)//2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "        doublenums = nums+nums \n",
    "        stack = []\n",
    "\n",
    "        ans = [-1]*(2*n)\n",
    "        for i in range(2*n):\n",
    "            if not stack:\n",
    "                stack.append((i,doublenums[i]))\n",
    "                continue \n",
    "            if stack[-1][1]>=doublenums[i]:\n",
    "                stack.append((i, doublenums[i]))\n",
    "                continue \n",
    "            else:\n",
    "                while stack and stack[-1][1]<doublenums[i]:\n",
    "                    index, x = stack[-1]\n",
    "    \n",
    "                    ans[index] = doublenums[i]\n",
    "                    stack.pop()\n",
    "\n",
    "                stack.append((i, doublenums[i]))\n",
    "               \n",
    "\n",
    "                \n",
    "        return ans[:n]             \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        ns = nums * 2\n",
    "        ans, stack = [-1] * len(ns), []\n",
    "        for i in range(len(ns)):\n",
    "            current = ns[i]\n",
    "            while stack and stack[-1][0] < current:\n",
    "                ans[stack.pop()[1]] = current\n",
    "            stack.append((current, i))\n",
    "        return ans[:len(nums)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        nums1 = nums * 2\n",
    "        stack = []\n",
    "        ans = [-1] * len(nums)\n",
    "        for i in range(len(nums1)):\n",
    "            if not stack:\n",
    "                stack.append([i, nums1[i]])\n",
    "            else:\n",
    "                while stack and stack[-1][1] < nums1[i]:\n",
    "                    ans[stack[-1][0] % len(ans)] = nums1[i]\n",
    "                    stack.pop()\n",
    "                stack.append([i, nums1[i]])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        decrease_stack = []\n",
    "        result_dict = {}\n",
    "        new_nums = nums + nums\n",
    "        for i in range(len(new_nums)):\n",
    "            while decrease_stack and new_nums[decrease_stack[-1]] < new_nums[i]:\n",
    "                t = decrease_stack.pop(-1)\n",
    "                if t < len(nums):\n",
    "                    result_dict[t] = (i - len(nums)) % len(nums)\n",
    "            decrease_stack.append(i)\n",
    "\n",
    "        while decrease_stack:\n",
    "            t = decrease_stack.pop(-1)\n",
    "            if t < len(nums) and t not in result_dict:\n",
    "                result_dict[t] = -1\n",
    "        result = []\n",
    "        for t in range(len(nums)):\n",
    "            if result_dict[t] > -1:\n",
    "                result.append(nums[result_dict[t]])\n",
    "            else:\n",
    "                result.append(-1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        a=[]\n",
    "        z=max(nums)\n",
    "        c=[]\n",
    "        for b in nums:\n",
    "            if b!=z:\n",
    "                c.append(b)\n",
    "            else:\n",
    "                c.append(-1)\n",
    "        for b in range(len(nums)):\n",
    "            while a and nums[b]>a[-1][1]:\n",
    "                c[a[-1][0]]=nums[b]\n",
    "                a.pop()\n",
    "            a.append([b,nums[b]])\n",
    "        for b in range(len(nums)):\n",
    "            if not a:\n",
    "                break\n",
    "            while nums[b]>a[-1][1]:\n",
    "                c[a[-1][0]]=nums[b]\n",
    "                a.pop()\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        slow,fast=0,0\n",
    "        ret=[None]*len(nums)\n",
    "        while slow<len(nums):\n",
    "            if ret[slow]!=None:\n",
    "                slow+=1\n",
    "                continue\n",
    "            judge=0\n",
    "            fast=(slow+1)%len(nums)\n",
    "            stack=[]\n",
    "            while nums[fast]<=nums[slow]:\n",
    "                if fast==slow and judge==1:\n",
    "                    break\n",
    "                judge=1\n",
    "                while len(stack)!=0 and nums[fast]>stack[-1][0]:\n",
    "                    ret[stack[-1][1]]=nums[fast]\n",
    "                    stack.pop()\n",
    "                stack.append([nums[fast],fast])\n",
    "                fast=(fast+1)%len(nums)\n",
    "            if fast==slow and judge==1:\n",
    "                ret[slow]=-1\n",
    "            else:\n",
    "                ret[slow]=nums[fast]\n",
    "            while len(stack)!=0:\n",
    "                val,i=stack.pop()\n",
    "                if val==nums[slow]:\n",
    "                    continue\n",
    "                ret[i]=nums[fast]\n",
    "            slow=fast\n",
    "\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
